Имеется n коробок, пронумерованных с 1 до n, а также n ключей, пронумерованных с 1 до n. i - ый ключ может
открыть только i - ую коробку.
Произвольным образом расположим каждый ключ в отдельную коробку, после чего
закроем все коробки. Считаем, что любое расположения ключей можно получить с
одинаковой вероятностью. Имеются m
бомб, каждой из которых можно открыть одну коробку. Открыв при помощи бомбы
коробку и достав из нее ключ, возможно, этим ключом можно открыть еще одну
коробку (если этот ключ не от коробки, в которой он лежал). Таким образом
продолжаем процесс подрыва коробок, доставания ключей и открывание коробок
извлеченными ключами.
Найти
вероятность того, что можно таким образом открыть все коробки.
Вход. Каждая строка содержит два целых числа n (1 ≤ n ≤ 20) и m (1
≤ m ≤ n).
Выход. Для каждого теста в отдельной строке вывести вероятность
того, что можно открыть все коробки. Выводить искомую вероятность следует в
виде дроби “A/B”. Значения A и B являются натуральными числами, не содержат
ведущих нулей и являются взаимно простыми.
|
Пример
входа |
Пример
выхода |
|
2 1 3 1 3 2 4 2 |
1/2 1/3 5/6 17/24 |
РЕШЕНИЕ
специальные числа – числа Стирлинга
Анализ алгоритма
Взорвав бомбой
коробку, можно достать ключ из другой коробки. Ключом из другой коробки можно
открыть следующую. И так далее, пока не будет вскрыта коробка, в которой лежит
ключ от первой коробки. Одной бомбой можно открыть такое множество коробок,
которые образуют цикл в перестановке ключей. Количество циклов в перестановке
ключей равно числу бомб, необходимых для открытия всех коробок.
Например, пусть
ключи образуют перестановку (2, 1, 3, 5, 4) = (12)(3)(45). Она состоит из трех циклов, поэтому
для извлечения всех ключей потребуется три бомбы.
Количество
перестановок из n элементов, имеющих
в точности k циклов, равно числу
Стирлинга первого рода s(n, k), которые вычисляются по рекуррентной
формуле:
s(n, k)
= s(n – 1, k – 1) + (n – 1) * s(n – 1, k)
Искомая
вероятность равна количеству разных перестановок, состоящих из не более чем m циклов, деленная на количество всех
перестановок n!.
В массиве
s[21][21] вычисляются числа Стирлинга, причем s[n][k] = s(n, k).
В переменной a вычисляется сумма s(n, 1) + s(n, 2) + … + s(n, m), в переменной b – число перестановок n!.
Возвращаем результат в виде строки “a/b”, предварительно сократив числитель и
знаменатель на их наибольший общий делитель.
Реализация алгоритма
Функция getAllKeys по заданным n и m
возвращает такие a и b, для которых a / b является вероятностью
того, что можно открыть все коробки.
void getAllKeys(int
n, int m, long long &a, long long &b)
{
int i, k;
long long d;
memset(s,0,sizeof(s));
s[0][0] = 1;
for(i = 1; i
<= n; i++)
for(k = 1;
k <= n; k++)
s[i][k] = s[i-1][k-1] + (i-1) *
s[i-1][k];
В переменной а вычисляем сумму s(n, 1)
+ s(n, 2) + ... + s(n, m)
for (a = 0, i
= 1; i <= m; i++) a += s[n][i];
В переменной b вычисляем факториал числа n.
for(b = i =
1; i <= n; i++) b *= i;
Сокращаем дробь a / b.
d = gcd(a,b); a /= d; b /= d;
}
Основной цикл программы.
while(scanf("%d
%d",&n,&m) == 2)
{
getAllKeys(n,m,a,b);
printf("%lld/%lld\n",a,b);
}